<?php
/**
 * User: LRZ
 * Date: 2020/1/16
 * Time: 11:53
 */

/**
 *  840.矩阵中的幻方
 *
 *  标签：数组
 *
 *  3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
 *  给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
 *
 *  示例：
 *      输入: [[4,3,8,4],
 *            [9,5,1,9],
 *            [2,7,6,2]]
 *      输出: 1
 *      解释:下面的子矩阵是一个 3 x 3 的幻方：
 *          438
 *          951
 *          276
 *      而这一个不是：
 *          384
 *          519
 *          762
 *      总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
 *
 *  提示:
 *      1 <= grid.length <= 10
 *      1 <= grid[0].length <= 10
 *      0 <= grid[i][j] <= 15
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/magic-squares-in-grid
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$grid = [
    [4, 3, 8, 4],
    [9, 5, 1, 9],
    [2, 7, 6, 2]
];
$res  = numMagicSquaresInside($grid);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function numMagicSquaresInside($grid)
{
    $R   = count($grid);
    $C   = count($grid[0]);
    $ans = 0;
    for ($r = 0; $r < $R - 2; $r++) {
        for ($c = 0; $c < $C - 2; $c++) {
            if ($grid[$r + 1][$c + 1] !== 5) {
                continue;
            }
            if (magic([
                $grid[$r][$c],
                $grid[$r][$c + 1],
                $grid[$r][$c + 2],
                $grid[$r + 1][$c],
                $grid[$r + 1][$c + 1],
                $grid[$r + 1][$c + 2],
                $grid[$r + 2][$c],
                $grid[$r + 2][$c + 1],
                $grid[$r + 2][$c + 2],
            ])) {
                $ans++;
            }
        }
    }
    return $ans;
}

function magic($array)
{
    $temp = [];
    foreach ($array as $k => $v) {
        $temp[$v] = 1;
    }

    for ($i = 1; $i < 10; $i++) {
        if (!isset($temp[$i])) {
            return false;
        }
    }

    return (
        $array[0] + $array[1] + $array[2] === 15 &&
        $array[3] + $array[4] + $array[5] === 15 &&
        $array[6] + $array[7] + $array[8] === 15 &&
        $array[0] + $array[3] + $array[6] === 15 &&
        $array[1] + $array[4] + $array[7] === 15 &&
        $array[2] + $array[5] + $array[8] === 15 &&
        $array[0] + $array[4] + $array[8] === 15 &&
        $array[2] + $array[4] + $array[6] === 15
    );
}